<!DOCTYPE html>
<html lang="en">

<head>
    <meta charset="UTF-8">
    <meta http-equiv="X-UA-Compatible" content="IE=edge">
    <meta name="viewport" content="width=device-width, initial-scale=1.0">
    <title>Document</title>
</head>

<body>
    <script>
        /* 
            示例 1:
                示例 1：

                输入：nums = [1,2,3], target = 4
                输出：7
                解释：
                所有可能的组合为：
                (1, 1, 1, 1)
                (1, 1, 2)
                (1, 2, 1)
                (1, 3)
                (2, 1, 1)
                (2, 2)
                (3, 1)
                请注意，顺序不同的序列被视作不同的组合。
                示例 2：

                输入：nums = [9], target = 3
                输出：0
        */
            
        /*
            经典递归套路，backTrack(target - nums[i])
            和零钱兑换的区别是，零钱兑换，必须每一层维护一个自己的startIndex，也就是他的顺序是固定的，能有1，3的组合，但是无3，1的组合

            时间复杂度：O(n ^ (target / minNum)),若minNum是1，则可能接近于O(n ^ target)，为什么是n的多次方，你就理解有很多个nums的for循环相乘，这样就理解了
            空间复杂度：O(n) 
        */
        var combinationSum4 = function(nums, target) {
            const backTrack = (target) => {
                // 退出条件
                if (target === 0) return 1 // 找到一个方案了
                let res = 0
                for (let i = 0; i < nums.length; i++) {
                    let num = nums[i]
                    // 继续拿其他数字
                    if (num > target) continue
                    // 这里递归
                    res += backTrack(target - num)
                }
                return res
            }
            return backTrack(target)
        }
        console.log(combinationSum4([1, 2, 3], 4));
    </script>
</body>

</html>